Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

So, herzlich willkommen zur heutigen Vorlesung. Letzte Woche, die zweite Vorlesung, haben Sie so

ein bisschen kombinatorische Werkzeuge, jetzt haben wir das überschrieben, kennengelernt,

ganz verschiedene grundsätzliche Prinzipien, wo man sagt, ja, auf den ersten Blick ist

es offensichtlich, wie sozusagen das Pitch and Hold Prinzip, dass wenn man n plus 1 Gegenstände

auf n Eimer verteilen will, dass in einem Eimer zwei Sachen sein müssen.

Das sind alles so offensichtliche Tricks.

Die Schwierigkeit ist immer, wenn man dann irgendwann mal was beweisen will und dann

braucht man halt immer genau den richtigen Trick und wenn man den dann hat, dann macht

es klack, das ist es.

Und wenn man den nicht hat, dann schwitzt man und versucht darum zu eiern.

Und es ist manchmal bei kombinatorischen Problemstellungen in der Tat der Fall, weil

man, wie man auch feststellen werden, die Kombinatorik einfach, viele sprechen von einer

kombinatorischen Explosion, wenn sie sozusagen die Anzahl Lösungen an sich wächst exponentiell

und manchmal doppelt exponentiell.

Das heißt, wenn sie jetzt irgendwelche anfangen, Fallunterscheidungen von Lösungen und so

weiter zu machen, dann verhaspen sie sich ziemlich sicher sehr schnell und finden genau

den entscheidenden Ansatz nicht.

Während wenn sie sozusagen auf die Dinge mit einem anderen Blickwinkel gucken, dann

macht es plötzlich, ok, ja, genau so ist es.

Wir haben im Kleinen das letzte Stunde geübt und auch im Kleinen schon die Stunde davor,

Beispiel auch mit dem 2 hoch n, die Anzahl möglicher n-k-elementiger Teilmengen, das

kann man sehr unterschiedlich angucken.

Wenn ich das Argument, ein einzelnes Element ist drin oder nicht drin, habe ich zwei Möglichkeiten,

n Stück, also 2 hoch n, oder ich sage k-Elemente rauszunehmen, da gibt es n über k Möglichkeiten

und also muss die Summe über alle n über k auch 2 hoch n sein.

Das sind komplett unterschiedliche Sichtweisen auf ein und denselben Sachverhalt und das

macht es manchmal schwierig, den richtigen Zugriff zu finden, auf der anderen Seite aber

auch spannend und gibt dann da an der einen oder anderen Stelle durchaus mal auch so ein

Aha-Erlebnis, was ich finde ich immer ganz nett an dem Gebiet an sich finde.

Gibt es zu der letzten Woche und den letzten zwei Stunden noch Nachfragen, welche Unklarheiten?

Gut, wenn das nicht der Fall ist, dann wollen wir uns heute die Grundlagen, ein Stück weit

in die Grundlagen der Grafentheorie bewegen, also wir schauen uns erstmal die Begrifflichkeiten

dort an, weil Grafen spielen eine sehr zentrale Rolle, also die meisten kombinatorischen Optimierungsprobleme,

die wir uns in den ersten paar Wochen anschauen, die spielen alle auf sogenannten Grafen und

im Grafen haben Sie mit Sicherheit wahrscheinlich schon oft gehört, das habe ich vielleicht

auch schon mal in der Schule gehabt, auch kommen in sehr unterschiedlichen Kontexten vor, deswegen

ist es wichtig, dass wir sozusagen eine einheitliche Begrifflichkeit und Notation auch haben, um

dann nachher auch besser differenzieren zu können.

Wir werden das am Beispiel der Wege sehen, was man leicht im Jargon oder auch in der Umgangssprache

– ich suche einen kürzesten Weg von A nach B, was denn eigentlich überhaupt jetzt rein

mathematisch ein Weg überhaupt ist und da wird man sehen, dass man aufpassen muss in

der Definition, denn je nachdem, ob ich zum Beispiel an einen Ort zurückkehren darf

oder nicht, wenn man mathematisch von einem Pfad sprechen und von einem Weg nur dann,

wenn das nicht der Fall ist und wir werden sehen, dass das von der Komplexitätsfrage

her durchaus einen richtigen Unterschied nachher macht, welche Fragestellungen man adressiert

und man vielleicht in der Umgangssprache erstmal gar keinen Unterschied sieht, aber mathematisch

wird es dann fein voneinander trennen müssen.

Und man wird sehen, dass es auch gleich schon, deswegen habe ich in dem Anfangskapitel gleich

schon so ein paar vielleicht ganz nette Beispiele mitgebracht.